翻訳と辞書 Words near each other ・ CIPHERUNICORN-A ・ CIPHERUNICORN-E ・ Cipiapa Formation ・ Cipinang Penitentiary Institution ・ Cipitio ・ Cipières ・ Cipla ・ Cipla Quality Chemical Industries Limited ・ Ciply ・ CIPO ・ Cipo canastero ・ Cipocereus ・ Cipocereus bradei ・ Cipolla ・ Cipolla di Giarratana ・ Cipolla's algorithm ・ Cipolletti ・ Cipollini ・ Cipollino ・ Cipollino marble ・ Cipollone v. Liggett Group, Inc. ・ Cipondoh ・ Cipotegato ・ Cipotânea ・ CIPP ・ CIPP evaluation model ・ Cippenham ・ Cippenham Moat ・ Cippi of Melqart ・ Cippico Castle Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Cipolla's algorithm ： ウィキペディア英語版 Cipolla's algorithm In computational number theory, Cipolla's algorithm is a technique for solving a congruence of the form :$x^2\backslash equiv\; n\; \backslash pmod,$ where $x,n\; \backslash in\; \backslash mathbf\_$, so ''n'' is the square of ''x'', and where $p$ is an odd prime. Here $\backslash mathbf\_p$ denotes the finite field with $p$ elements; $\backslash$. The algorithm is named after Michele Cipolla, an Italian mathematician who discovered it in 1907. ==Algorithm== Inputs: * $p$, an odd prime, * $n\; \backslash in\; \backslash mathbf\_p$, which is a square. Outputs: * $x\; \backslash in\; \backslash mathbf\_p$, satisfying $x^2=\; n\; .$ Step 1 is to find an $a\; \backslash in\; \backslash mathbf\_p$ such that $a^2\; -\; n$ is not a square. There is no known algorithm for finding such an $a$, except the trial and error method. Simply pick an $a$ and by computing the Legendre symbol $(a^2-n|p)$ one can see whether $a$ satisfies the condition. The chance that a random $a$ will satisfy is $(p-1)/2p$. With $p$ large enough this is about $1/2$.〔R. Crandall, C. Pomerance Prime Numbers: A Computational Perspective Springer-Verlag, (2001) p. 157〕 Therefore, the expected number of trials before finding a suitable ''a'' is about 2. Step 2 is to compute ''x'' by computing $x=\backslash left(\; a\; +\; \backslash sqrt\; \backslash right)^$ within the field $\backslash mathbf\_\; =\; \backslash mathbf\_p(\backslash sqrt)$. This ''x'' will be the one satisfying $x^2\; =n\; .$ If $x^2\; =\; n$, then $(-x)^2\; =\; n$ also holds. And since ''p'' is odd, $x\; \backslash neq\; -x$. So whenever a solution ''x'' is found, there's always a second solution, ''-x''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Cipolla's algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.